package com.salim.leetcode.$101;

import com.salim.leetcode.util.TreeNode;
import com.salim.leetcode.util.TreeNodeUtils;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * https://leetcode.com/problems/symmetric-tree/
 */
@Slf4j
public class SymmetricTree2 {

    /**
     * 思路2 广度优先
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        LinkedList<TreeNode> leftCurrentLevel = new LinkedList<>();
        leftCurrentLevel.add(root.left);
        LinkedList<TreeNode> rightCurrentLevel = new LinkedList<>();
        rightCurrentLevel.addLast(root.right);
        while (leftCurrentLevel!=null && !leftCurrentLevel.isEmpty()){
            int leftCurrentLength = leftCurrentLevel.size();
            if(leftCurrentLength!=rightCurrentLevel.size()){
                return false;
            }
            for(int i=0;i<leftCurrentLength;i++){
                TreeNode leftCurrent = leftCurrentLevel.getFirst();
                TreeNode rightCurrent = rightCurrentLevel.getLast();
                if((leftCurrent==null && rightCurrent!=null) || (leftCurrent!=null && rightCurrent == null)){
                    return false;
                }
                if(leftCurrent==null && rightCurrent==null){
                    leftCurrentLevel.removeFirst();
                    rightCurrentLevel.removeLast();
                    continue;
                }

                if(leftCurrent.val != rightCurrent.val){
                    return false;
                }

                leftCurrentLevel.removeFirst();
                leftCurrentLevel.add(leftCurrent.left);
                leftCurrentLevel.add(leftCurrent.right);

                rightCurrentLevel.removeLast();
                rightCurrentLevel.addFirst(rightCurrent.right);
                rightCurrentLevel.addFirst(rightCurrent.left);
            }
        }
        return true;
    }

    public static void main(String[] args){
        Integer[] arr = {2,3,3,4,5,5,4,null,null,8,9,9,8};
        TreeNode root = TreeNodeUtils.generateTreeNode(arr);
        SymmetricTree2 tree = new SymmetricTree2();
        log.info("{2,3,3,4,5,5,4,null,null,8,9,9,8},{}",tree.isSymmetric(root));
        Integer[] arr2 = {1,2,2,3,4,4,3};
        root = TreeNodeUtils.generateTreeNode(arr2);
        log.info("{1,2,2,3,4,4,3},{}",tree.isSymmetric(root));
        Integer[] arr3 = {1,2,2,null,3,null,3};
        root = TreeNodeUtils.generateTreeNode(arr3);
        log.info("{1,2,2,null,3,null,3},{}",tree.isSymmetric(root));
    }
}

